import java.util.*;

public class BreadthFirstSearch {
	public static List<State> solve(State start, State goal) {
		// FIFO collection of nodes that have not been explored.
		Queue<State> frontier = new LinkedList<>();
		// Collection (with fast search) holding nodes that have been explored or
		// are already in the frontier.  Each node maps to its parent node, for the
		// purposes of tracing and displaying the solution path.
		Map<State,State> exploredAndFrontier = new HashMap<>();
		// The total number of nodes explored.
		int nodesExplored = 0;
		// The total number of nodes that have been in the frontier.
		int nodesInFrontier = 0;
		// The total number of nodes created.
		int nodesCreated = 0;
		// The path to the goal node.
		List<State> path = new LinkedList<State>();

		frontier.add(start);
		exploredAndFrontier.put(start, null);
		nodesInFrontier++;
		
outer:	while (!frontier.isEmpty()) {
	
			State node = frontier.remove();
			nodesExplored++;
			
			for (State child : node.getNeighbors()) {
				nodesCreated++;
				
				if (!exploredAndFrontier.containsKey(child)) {
					
					frontier.add(child);
					exploredAndFrontier.put(child, node);
					nodesInFrontier++;
					
					if (child.equals(goal)) {
						
						
						path = createPath(child, exploredAndFrontier);
						displaySolutionPath(child, exploredAndFrontier, path);
						break outer;
					}
				}
			}
			
			System.out.println("Frontier: \n" + frontier.toString() + "\n");
		}
		
		System.out.println("   Nodes explored: " + nodesExplored);
		System.out.println("Nodes in frontier: " + nodesInFrontier);
		System.out.println("    Nodes created: " + nodesCreated);
		
		return path;
	}
	
	public static void displaySolutionPath(State node, Map<State,State> parentMap, List<State> path) {
		
		System.out.println("\n\n\n\n\n");
		System.out.println("---------- Solution Found ----------");
		

		for (State puzzle : path)
			System.out.println(puzzle);
		System.out.println("Solution in " + (path.size() - 1) + " moves.");
	}
	
	/**
	 * Creates a list representing the path to the node holding the goal state.
	 * 
	 * @param node The node that contains the goal state.
	 * @param parentMap The collection holding the nodes of the current search path.
	 * @return A list representing the path to the node holding the goal state.
	 */
	private static List<State> createPath(State node, Map<State,State> parentMap) {
		
		LinkedList<State> path = new LinkedList<>();
		
		while (node != null) {
			path.addFirst(node);
			node = parentMap.get(node);
		}
		return path;
	}
}
